Big-Theta Notation

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Computational Complexity #◇Efficiency #◇Algorithm Design Paradigms #◇Data Structures #◇Time Complexity #◇Space Complexity

---

◇Overview

f(n) = Θ(g(n)) means f(n) grows at the same rate as g(n).

◇Details / Theory

Asymptotic Tight Bound

f(n) = Θ(g(n)) means f(n) grows at the same rate as g(n). This represents the Average-case running time of an algorithm. Requires f(n) = O(g(n)) AND f(n) = Ω(g(n)).
Means that we need to get Big-Oh$(O)$ and Big-Omega $(\Omega)$ Formal Definition: $Θ(g(n)) = { f(n) | ∃ c₁, c₂ > 0, n₀ > 0\text{ such that}\ 0 ≤ c₁⋅g(n) ≤ f(n) ≤ c₂⋅g(n)\ \text{for all}\ n ≥ n₀ }$ (Handout 03, Page 5)
Example: $6n³ + 2n² + 3n + 8$ is $Θ(n³)$.
Since it is also both $\Omega(n^3)$ and $O(n^3)$, it is also $\Theta(n^3)$

◇Complexity

◇Common Pitfalls

Forgetting that $\Theta$ requires BOTH $O$ and $\Omega$ to hold — it’s a tight bound. Using $\Theta$ when only an upper bound is known — use $O$ instead if $\Omega$ hasn’t been established.

◇Summary

TL;DR — Big-Theta ($\Theta$) gives an asymptotic tight bound: $f(n) = \Theta(g(n))$ means $f(n)$ grows at the same rate as $g(n)$. Requires both $O(g(n))$ and $\Omega(g(n))$.

◇Links

Related: Source / Reference:

◇References & Navigation

• Previous Topic: ◇Big-Omega Notation
• Next Topic: ◇Conditionals
• Related Notes: ◇Big-O Notation, ◇Big-Omega Notation